Reading list for Wed, Sep.25, 2024

Total: 771 from which: 3 suggested today and 564 expired

Today's reading list ±

3 links selected from 207 today Wed, Sep.25, 2024
  1. Concurrency Freaks: 50 years later, is Two-Phase Locking the best we can do?

    Two phase locking (2PL) was the first of the general-purpose Concurrency Controls to be invented which provided Serializability. In fact, 2PL gives more than Serializability, it gives Opacity, a much stronger isolation l ... (12997 chars. See body)


    Two phase locking (2PL) was the first of the general-purpose Concurrency Controls to be invented which provided Serializability. In fact, 2PL gives more than Serializability, it gives Opacity, a much stronger isolation level.
    2PL was published in 1976, which incidentally is the year I was born, and it is likely that Jim Gray and his buddies had this idea long before it was published, which means 2PL first came to existence nearly 50 years ago.
    Jim Gray Endowed Scholarship | Paul G. Allen School of Computer Science &  Engineering

    After all that time has passed, is this the best we can do?

     Turns out no, we can do better with 2PLSF, but let's start from the begining

    When I use the term "general-purpose concurrency control" I mean an algorithm which allows access multiple objects (or records or tuples, whatever you want to name them) with an all-or-nothing semantics. In other words, an algorithm that lets you do transactions over multiple data items.
    Two-Phase Locking has several advantages over the other concurrency controls that have since been invented, but in my view there are two important ones: simplicity and a strong isolation level.

    In 2PL, before accessing a record for read or write access, we must first take the lock that protects this record.
    During the transaction, we keep acquiring locks for each access, and only at the end of the transaction, when we know that no further accesses will be made, can we release all the locks. Having an instant in time (i.e. the end of the transaction) where all the locks are taken on the data that we accessed, means that there is a linearization point for our operation (transaction), which means we have a consistent view of the different records and can write to other records all in a consistent way. It doesn't get much simpler than this.
    Today, this idea may sound embarrassingly obvious, but 50 years ago many database researchers thought that it was ok to release the locks after completing the access to the record. And yes, it is possible to do so, but such a concurrency control is not serializable.

    As for strong isolation, database researchers continue to invent concurrency controls that are not serializable, and write papers about it, which means Serializability is not that important for Databases. On the other hand, all transactional commercial databases that I know of, use 2PL or some combination of it with T/O or MVCC.

    Moreover, in the field of concurrency data structures, linearizability is the gold standard, which means 2PL is used heavily. If we need to write to multiple nodes of a data structure in a consistent way, we typically need something like 2PL, at least for the write accesses. The exception to this are lock-free data-structures, but hey, that's why (correct) lock-free is hard!

    Ok, 2PL is easy to use and has strong isolation, so this means we're ready to go and don't need anything better than 2PL, right?
    I'm afraid not. 2PL has a couple of big disadvantages: poor read-scalability and live-lock progress.

    The classic 2PL was designed for mutual exclusion locks, which means that when two threads are performing a read-access on the same record, they will conflict and one of them (or both) will abort and restart.
    This problem can be solved by replacing the mutual exclusion locks with reader-writer locks, but it's not as simple as this.
    Mutual exclusion locks can be implemented with a single bit, representing the state of locked or unlocked.
    Reader-writer locks also need this bit and in addition, need to have a counter of the number of readers currently holding the lock in read mode. This counter needs enough bits to represent the number of readers. For example, 7 bits means you can have a maximum of 128 threads in the system, in case they all decide to acquire the read-lock on a particular reader-writer lock instance.
    For such a scenario this implies that each lock would take 1 byte, which may not sound like much, but if you have billions of records in your DB then you will need billions of bytes for those locks. Still reasonable, but now we get into the problem of contention on the counter.

    Certain workloads have lots of read accesses on the same data, they are read-non-disjoint. An example of this is the root node of a binary search tree, where all operations need to read the root before they start descending the nodes of the tree.
    When using 2PL, each of these accesses on the root node implies a lock acquisition and even if we're using read-writer locks, it implies heavy contention on the lock that protects the root node.

    Previous approaches have taken a stab at this problem, for example TLRW by Dave Dice and Nir Shavit in SPAA 2010.
    By using reader-writer locks they were able to have much better performance than using mutual exclusion locks, but still far from what the optimistic concurrency controls can achieve.
    Take the example of the plot below where we have an implementation similar to TLRW with each read-access contending on a single variable of the reader-writer lock, applied to a binary search tree, a Rank-based Relaxed AVL. Scalability is flat regardless of whether we're doing mostly write-transactions (left side plot) or just read-transactions (right side plot).

    Turns out it is possible to overcome this "read-indicator contention" problem through the usage of scalable read-indicators. Our favorite algorithm is a reader-writer lock where each reader announces its arrival/departure on a separate cache line, thus having no contention for read-lock acquisition. The downside is that the thread taking the write-lock must scan through all those cache lines to be able to ascertain whether if the write-lock is granted, thus incurring a higher cost for the write-lock acquisition.
    As far as I know, the first reader-writer lock algorithms with this technique were shown in the paper "NUMA Aware reader-writer locks" of which Dave Dice and Nir Shavit are two of the authors, along with Irina Calciu, Yossi Lev, Victor Luchangco, and Virenda Marathe
    This paper shows three different reader-writer lock algorithms, two with high scalability, but neither is starvation-free.

    So what we did was take some of these ideas to make a better reader-writer lock, which also scales well for read-lock acquisition but has other properties, and we used this to implement our own concurrency control which we called Two-Phase Locking Starvation-Free (2PLSF).
    The reader-writer locks in 2PLSF have one bit per thread reserved for the read-lock but they are located in their own cache line, along with the bits (read-indicators) of the next adjacent locks.


    Like on the "NUMA-Aware reader-writer locks" paper, the cost shifts to the write-lock acquisition which needs to scan multiple cache lines to acquire the write-lock. There is no magic here, just trade-offs, but this turns out to be a pretty good trade-off as most workloads tend to be on the read-heavy side. Even write-intensive workloads spend a good amount of time executing read-accesses, for example, during the record lookup phase.
    With our improved reader-writer lock the same benchmark shown previously for the binary search tree looks very different:

    With this improved reader-writer lock we are able to scale 2PL even on read-non-disjoint workloads, but it still leaves out the other major disadvantage, 2PL is prone to live-lock.

    There are several variants of the original 2PL, some of these variants aren't even serializable, therefore I wouldn't call them 2PL anymore and won't bother going into that.
    For the classical 2PL, there are three variants and they are mostly about how to deal with contention. They're usually named:
        - No-Wait
        - Wait-Or-Die
        - Deadlock-detection

    When a conflict is encountered, the No-Wait variant aborts the self transaction (or the other transaction) and retries again. This retry can be immediate, or it can be later, based on an exponential backoff scheme. The No-Wait approach has live-lock progress because two transactions with one attempting to modify record A and then record B, while the other is attempting to modify record B and then record A, may indefinitely conflict with each other and abort-restart without any of them ever being able to commit.

    The Deadlock-Detection variant keeps an internal list of threads waiting on a lock and detects cycles (deadlocks).
    This is problematic for reader-writer locks because it would require each reader to have its own list, which itself needs a (mutual exclusion) lock to protect it. And detecting the cycles would mean scanning all the readers' lists when the lock is taken in read-lock mode.
    Theoretically it should be possible to make this scheme starvation-free, but it would require using starvation-free locks, and as there is no (published) highly scalable reader-writer lock with starvation-free progress, it kind of defeats the purpose. Moreover, having one list per reader may have consequences on high memory usage. Who knows, maybe one day someone will try this approach.

    The Wait-Or-Die variant imposes an order on all transactions, typically with a timestamp of when the transaction started and, when a lock conflict arises, decides to wait for the lock or to abort, by comparing the timestamp of the transaction with the timestamp of the lock owner. This works fine for mutual exclusion locks as the owner can be stored in the lock itself using a unique-thread identifier, but if we want to do it for reader-writer locks then a thread-id would be needed per reader.
    If we want to support 256 threads then this means we need 8 bits x 256 = 256 bytes per reader-writer lock. Using 256 bytes per lock is a hard pill to swallow!

    But memory usage is not the real obstacle here. The Wait-Or-Die approach implies that all transactions have a unique transaction id so as to order them, for example, they can take a number from an atomic variable using a fetch_and_add() instruction.
    The problem with this is that on most modern CPUs you won't be able to do more than 40 million fetch_and_add() operations per second on a contended atomic variable. This may seem like a lot (Visa does about 660 million transactions per day, so doing 40 million per second sounds pretty good), but when it comes to in-memory DBMS it's not that much, and particularly for concurrent data structures is a bit on the low side.
    Even worse, this atomic fetch_and_add() must be done for all transactions, whether they are write-transactions or read-transactions.
    For example, in one of our machines it's not really possible to go above 20 M fetch_and_add() per second, which means that scalability suckz:

    To put this in perspective, one of my favorite concurrency controls is TL2 which was invented by (surprise!) none other than Dave Dice, Nir Shavit and Ori Shalev
    I hope by now you know who are the experts in this stuff  ;)

    Anyways, in TL2 the read-transactions don't need to do an atomic fetch_and_add(), and they execute optimistic reads, which is faster than any read-lock acquisition you can think of. At least for read-transactions, TL2 can scale to hundreds of millions of transactions per second. By comparison, 2PL with Wait-Or-Die will never be able to go above 40 M tps/sec.
    This means if high scalability is your goal, then you would be better off with TL2 than 2PL… except, 2PLSF solves this problem too.

    In 2PLSF only the transactions that go into conflict need to be ordered, i.e. only these need to do a fetch_and_add() on a central atomic variable. This has two benefits: it means there is less contention on the central atomic variable that assigns the unique transaction id, and it means that transactions without conflicts are not bounded by the 40 M tps plateau.
    This means that we can have 200 M tps running without conflict and then 40 M tps that are having conflict, because the conflicting transactions are the only ones that need to do the fetch_and_add() and therefore, and the only ones bounded by the maximum number of fetch_and_adds() the CPU can execute per second.
    On top of this, the 2PLSF algorithm provides starvation-freedom.

    Summary

    In this post we saw some of the advantages and disadvantages of 2PL and some of the variants of 2PL.
    We explained what it takes to scale 2PL: make a better reader-writer lock.
    But the big disadvantage of 2PL is the live-lock progress, which some variants could seemingly resolve, but in practice they don't because they will not scale, even with a better reader-writer lock.
    Then we described 2PLSF, a novel algorithm invented by me, Andreia and Pascal Felber to address these issues.

    In summary, 2PLSF is what 2PL should have been from the start, a concurrency control that scales well even when reads are non-disjoint and that provides starvation-free transactions, the highest form of blocking progress there is.
    Moreover, it's pretty good a solving certain kinds of conflicts, which means it can have scalability even some conflicts arise. 2PLSF is not perfect, but it's good enough, certainly better than TL2 when it comes to solving conflicts.

    Despite being two-phase locking, it's as close to 2PL as a jackhammer is to a pickaxe. 

    2PLSF is not your grandfather's 2PL



  2. Everything You Always Wanted to Know About Type Inference - And a Little Bit More

    A description of how type inference for Go works. Based on the GopherCon 2023 talk with the same title. ... (36615 chars. See body)


    This is the blog version of my talk on type inference at GopherCon 2023 in San Diego, slightly expanded and edited for clarity.

    What is type inference?

    Wikipedia defines type inference as follows:

    Type inference is the ability to automatically deduce, either partially or fully, the type of an expression at compile time. The compiler is often able to infer the type of a variable or the type signature of a function, without explicit type annotations having been given.

    The key phrase here is “automatically deduce … the type of an expression”. Go supported a basic form of type inference from the start:

    const x = expr  // the type of x is the type of expr
    var x = expr
    x := expr
    

    No explicit types are given in these declarations, and therefore the types of the constant and variables x on the left of = and := are the types of the respective initialization expressions, on the right. We say that the types are inferred from (the types of) their initialization expressions. With the introduction of generics in Go 1.18, Go’s type inference abilities were significantly expanded.

    Why type inference?

    In non-generic Go code, the effect of leaving away types is most pronounced in a short variable declaration. Such a declaration combines type inference and a little bit of syntactic sugar—the ability to leave away the var keyword—into one very compact statement. Consider the following map variable declaration:

    var m map[string]int = map[string]int{}
    

    vs

    m := map[string]int{}
    

    Omitting the type on the left of := removes repetition and at the same time increases readability.

    Generic Go code has the potential to significantly increase the number of types appearing in code: without type inference, each generic function and type instantiation requires type arguments. Being able to omit them becomes even more important. Consider using the following two functions from the new slices package:

    package slices
    func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool)
    func Sort[S ~[]E, E cmp.Ordered](x S)
    

    Without type inference, calling BinarySearch and Sort requires explicit type arguments:

    type List []int
    var list List
    slices.Sort[List, int](list)
    index, found := slices.BinarySearch[List, int](list, 42)
    

    We’d rather not repeat [List, int] with each such generic function call. With type inference the code simplifies to:

    type List []int
    var list List
    slices.Sort(list)
    index, found := slices.BinarySearch(list, 42)
    

    This is both cleaner and more compact. In fact it looks exactly like non-generic code, and type inference makes this possible.

    Importantly, type inference is an optional mechanism: if type arguments make code clearer, by all means, write them down.

    Type inference is a form of type pattern matching

    Inference compares type patterns, where a type pattern is a type containing type parameters. For reasons that will become obvious in a bit, type parameters are sometimes also called type variables. Type pattern matching allows us to infer the types that need to go into these type variables. Let’s consider a short example:

    // From the slices package
    // func Sort[S ~[]E, E cmp.Ordered](x S)
    
    type List []int
    var list List
    slices.Sort(list)
    

    The Sort function call passes the list variable as function argument for the parameter x of slices.Sort. Therefore the type of list, which is List, must match the type of x, which is type parameter S. If S has the type List, this assignment becomes valid. In reality, the rules for assignments are complicated, but for now it’s good enough to assume that the types must be identical.

    Once we have inferred the type for S, we can look at the type constraint for S. It says—because of the tilde ~ symbol—that the underlying type of S must be the slice []E. The underlying type of S is []int, therefore []int must match []E, and with that we can conclude that E must be int. We’ve been able to find types for S and E such that corresponding types match. Inference has succeeded!

    Here’s a more complicated scenario where we have a lot of type parameters: S1, S2, E1, and E2 from slices.EqualFunc, and E1 and E2 from the generic function equal. The local function foo calls slices.EqualFunc with the equal function as an argument:

    // From the slices package
    // func EqualFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, eq func(E1, E2) bool) bool
    
    // Local code
    func equal[E1, E2 comparable](E1, E2) bool { … }
    
    func foo(list1 []int, list2 []float64) {
        …
        if slices.EqualFunc(list1, list2, equal) {
            …
        }
        …
    }
    

    This is an example where type inference really shines as we can potentially leave away six type arguments, one for each of the type parameters. The type pattern matching approach still works, but we can see how it may get complicated quickly because the number of type relationships is proliferating. We need a systematic approach to determine which type parameters and which types get involved with which patterns.

    It helps to look at type inference in a slightly different way.

    Type equations

    We can reframe type inference as a problem of solving type equations. Solving equations is something that we are all familiar with from high school algebra. Luckily, solving type equations is a simpler problem as we will see shortly.

    Let’s look again at our earlier example:

    // From the slices package
    // func Sort[S ~[]E, E cmp.Ordered](x S)
    
    type List []int
    var list List
    slices.Sort(list)
    

    Inference succeeds if the type equations below can be solved. Here stands for is identical to, and under(S) represents the underlying type of S:

    S ≡ List        // find S such that S ≡ List is true
    under(S) ≡ []E  // find E such that under(S) ≡ []E is true
    

    The type parameters are the variables in the equations. Solving the equations means finding values (type arguments) for these variables (type parameters), such that the equations become true. This view makes the type inference problem more tractable because it gives us a formal framework that allows us to write down the information that flows into inference.

    Being precise with type relations

    Until now we have simply talked about types having to be identical. But for actual Go code that is too strong a requirement. In the previous example, S need not be identical to List, rather List must be assignable to S. Similarly, S must satisfy its corresponding type constraint. We can formulate our type equations more precisely by using specific operators that we write as :≡ and :

    S :≡ List         // List is assignable to S
    S ∈ ~[]E          // S satisfies constraint ~[]E
    E ∈ cmp.Ordered   // E satisfies constraint cmp.Ordered
    

    Generally, we can say that type equations come in three forms: two types must be identical, one type must be assignable to the other type, or one type must satisfy a type constraint:

    X ≡ Y             // X and Y must be identical
    X :≡ Y            // Y is assignable to X
    X ∈ Y             // X satisfies constraint Y
    

    (Note: In the GopherCon talk we used the symbols A for :≡ and C for . We believe :≡ more clearly evokes an assignment relation; and directly expresses that the type represented by a type parameter must be an element of its constraint’s type set.)

    Sources of type equations

    In a generic function call we may have explicit type arguments, though most of the time we hope that they can be inferred. Typically we also have ordinary function arguments. Each explicit type argument contributes a (trivial) type equation: the type parameter must be identical to the type argument because the code says so. Each ordinary function argument contributes another type equation: the function argument must be assignable to its corresponding function parameter. And finally, each type constraint provides a type equation as well by constraining what types satisfy the constraint.

    Altogether, this produces n type parameters and m type equations. In contrast to basic high school algebra, n and m don’t have to be the same for type equations to be solvable. For instance, the single equation below allows us to infer the type arguments for two type parameters:

    map[K]V ≡ map[int]string  // K ➞ int, V ➞ string (n = 2, m = 1)
    

    Let’s look at each of these sources of type equations in turn:

    1. Type equations from type arguments

    For each type parameter declaration

    func f[…, P constraint, …]…
    

    and explicitly provided type argument

    f[…, A, …]…
    

    we get the type equation

    P ≡ A
    

    We can trivially solve this for P: P must be A and we write P ➞ A. In other words, there is nothing to do here. We could still write down the respective type equation for completeness, but in this case, the Go compiler simply substitutes the type arguments for their type parameters throughout and then those type parameters are gone and we can forget about them.

    2. Type equations from assignments

    For each function argument x passed to a function parameter p

    f(…, x, …)
    

    where p or x contain type parameters, the type of x must be assignable to the type of the parameter p. We can express this with the equation

    𝑻(p) :≡ 𝑻(x)
    

    where 𝑻(x) means “the type of x”. If neither p nor x contains type parameters, there is no type variable to solve for: the equation is either true because the assignment is valid Go code, or false if the code is invalid. For this reason, type inference only considers types that contain type parameters of the involved function (or functions).

    Starting with Go 1.21, an uninstantiated or partially instantiated function (but not a function call) may also be assigned to a function-typed variable, as in:

    // From the slices package
    // func Sort[S ~[]E, E cmp.Ordered](x S)
    
    var intSort func([]int) = slices.Sort
    

    Analogous to parameter passing, such assignments lead to a corresponding type equation. For this example it would be

    𝑻(intSort) :≡ 𝑻(slices.Sort)
    

    or simplified

    func([]int) :≡ func(S)
    

    together with equations for the constraints for S and E from slices.Sort (see below).

    3. Type equations from constraints

    Finally, for each type parameter P for which we want to infer a type argument, we can extract a type equation from its constraint because the type parameter must satisfy the constraint. Given the declaration

    func f[…, P constraint, …]…
    

    we can write down the equation

    P ∈ constraint
    

    Here, the means “must satisfy constraint” which is (almost) the same as being a type element of the constraint’s type set. We will see later that some constraints (such as any) are not useful or currently cannot be used due to limitations of the implementation. Inference simply ignores the respective equations in those cases.

    Type parameters and equations may be from multiple functions

    In Go 1.18, inferred type parameters had to all be from the same function. Specifically, it was not possible to pass a generic, uninstantiated or partially instantiated function as a function argument, or assign it to a (function-typed) variable.

    As mentioned earlier, in Go 1.21 type inference also works in these cases. For instance, the generic function

    func myEq[P comparable](x, y P) bool { return x == y }
    

    can be assigned to a variable of function type

    var strEq func(x, y string) bool = myEq  // same as using myEq[string]
    

    without myEq being fully instantiated, and type inference will infer that the type argument for P must be string.

    Furthermore, a generic function may be used uninstantiated or partially instantiated as an argument to another, possibly generic function:

    // From the slices package
    // func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S
    
    type List []int
    var list List
    result := slices.CompactFunc(list, myEq)  // same as using slices.CompactFunc[List, int](list, myEq[int])
    

    In this last example, type inference determines the type arguments for CompactFunc and myEq. More generally, type parameters from arbitrarily many functions may need to be inferred. With multiple functions involved, type equations may also be from or involve multiple functions. In the CompactFunc example we end up with three type parameters and five type equations:

    Type parameters and constraints:
        S ~[]E
        E any
        P comparable
    
    Explicit type arguments:
        none
    
    Type equations:
        S :≡ List
        func(E, E) bool :≡ func(P, P) bool
        S ∈ ~[]E
        E ∈ any
        P ∈ comparable
    
    Solution:
        S ➞ List
        E ➞ int
        P ➞ int
    

    Bound vs free type parameters

    At this point we have a clearer understanding of the various source of type equations, but we have not been very precise about which type parameters to solve the equations for. Let’s consider another example. In the code below, the function body of sortedPrint calls slices.Sort for the sorting part. sortedPrint and slices.Sort are generic functions as both declare type parameters.

    // From the slices package
    // func Sort[S ~[]E, E cmp.Ordered](x S)
    
    // sortedPrint prints the elements of the provided list in sorted order.
    func sortedPrint[F any](list []F) {
        slices.Sort(list)  // 𝑻(list) is []F
        …                  // print list
    }
    

    We want to infer the type argument for the slices.Sort call. Passing list to parameter x of slices.Sort gives rise to the equation

    𝑻(x) :≡ 𝑻(list)
    

    which is the same as

    S :≡ []F
    

    In this equation we have two type parameters, S and F. Which one do we need to solve the type equation for? Because the invoked function is Sort, we care about its type parameter S, not the type parameter F. We say that S is bound to Sort because it is declared by Sort. S is the relevant type variable in this equation. By contrast, F is bound to (declared by) sortedPrint. We say that F is free with respect to Sort. It has its own, already given type. That type is F, whatever that is (determined at instantiation time). In this equation, F is already given, it is a type constant.

    When solving type equations we always solve for the type parameters bound to the function we are calling (or assigning in case of a generic function assignment).

    Solving type equations

    The missing piece, now that we have established how to collect the relevant type parameters and type equations, is of course the algorithm that allows us to solve the equations. After the various examples, it probably has become obvious that solving X ≡ Y simply means comparing the types X and Y recursively against each other, and in the process determining suitable type arguments for type parameters that may occur in X and Y. The goal is to make the types X and Y identical. This matching process is called unification.

    The rules for type identity tell us how to compare types. Since bound type parameters play the role of type variables, we need to specify how they are matched against other types. The rules are as follows:

    • If type parameter P has an inferred type, P stands for that type.
    • If type parameter P doesn’t have an inferred type and is matched against another type T, P is set to that type: P ➞ T. We say that the type T was inferred for P.
    • If P matches against another type parameter Q, and neither P nor Q have an inferred type yet, P and Q are unified.

    Unification of two type parameters means that they are joined together such that going forward they both denote the same type parameter value: if one of P or Q is matched against a type T, both P and Q are set to T simultaneously (in general, any number of type parameters may be unified this way).

    Finally, if two types X and Y are different, the equation cannot be made true and solving it fails.

    Unifying types for type identity

    A few concrete examples should make this algorithm clear. Consider two types X and Y containing three bound type parameters A, B, and C, all appearing in the type equation X ≡ Y. The goal is to the solve this equation for the type parameters; i.e., find suitable type arguments for them such that X and Y become identical and thus the equation becomes true.

    X: map[A]struct{i int; s []B}
    Y: map[string]struct{i C; s []byte}
    

    Unification proceeds by comparing the structure of X and Y recursively, starting at the top. Simply looking at the structure of the two types we have

    map[…]… ≡ map[…]…
    

    with the representing the respective map key and value types that we’re ignoring at this step. Since we have a map on both sides, the types are identical so far. Unification proceeds recursively, first with the key types which are A for the X map, and string for the Y map. Corresponding key types must be identical, and from that we can immediately infer that the type argument for A must be string:

    A ≡ string => A ➞ string
    

    Continuing with the map element types, we arrive at

    struct{i int; s []B} ≡ struct{i C; s []byte}
    

    Both sides are structs so unification proceeds with the struct fields. They are identical if they are in the same order, with the same names, and identical types. The first field pair is i int and i C. The names match and because int must unify with C, thus

    int ≡ C => C ➞ int
    

    This recursive type matching continues until the tree structure of the two types is fully traversed, or until a conflict appears. In this example, eventually we end up with

    []B ≡ []byte => B ≡ byte => B ➞ byte
    

    Everything works out fine and unification infers the type arguments

    A ➞ string
    B ➞ byte
    C ➞ int
    

    Unifying types with different structures

    Now, let’s consider a slight variation of the previous example: here X and Y don’t have the same type structure. When the type trees are compared recursively, unification still successfully infers the type argument for A. But the value types of the maps are different and unification fails.

    X: map[A]struct{i int; s []B}
    Y: map[string]bool
    

    Both X and Y are map types, so unification proceeds recursively as before, starting with the key types. We arrive at

    A ≡ string => A ➞ string
    

    also as before. But when we proceed with the map’s value types we have

    struct{…} ≡ bool
    

    The struct type doesn’t match bool; we have different types and unification (and thus type inference) fails.

    Unifying types with conflicting type arguments

    Another kind of conflict appears when different types match against the same type parameter. Here we have again a version of our initial example but now the type parameter A appears twice in X, and C appears twice in Y.

    X: map[A]struct{i int; s []A}
    Y: map[string]struct{i C; s []C}
    

    The recursive type unification works out fine at first and we have the following pairings of type parameters and types:

    A   ≡ string => A ➞ string  // map key type
    int ≡ C      => C ➞ int     // first struct field type
    

    When we get to the second struct field type we have

    []A ≡ []C => A ≡ C
    

    Since both A and C have a type argument inferred for them, they stand for those type arguments, which are string and int respectively. These are different types, so A and C can’t possibly match. Unification and thus type inference fails.

    Other type relations

    Unification solves type equations of the form X ≡ Y where the goal is type identity. But what about X :≡ Y or X ∈ Y?

    A couple of observations help us out here: The job of type inference is solely to find the types of omitted type arguments. Type inference is always followed by type or function instantiation which checks that each type argument actually satisfies its respective type constraint. Finally, in case of a generic function call, the compiler also checks that function arguments are assignable to their corresponding function parameters. All of these steps must succeed for the code to be valid.

    If type inference is not precise enough it may infer an (incorrect) type argument where no type may exist. If that is the case, either instantiation or argument passing will fail. Either way, the compiler will produce an error message. It’s just that the error message may be slightly different.

    This insight allows us to play a bit loose with the type relations :≡ and . Specifically, it allows us to simplify them such that they can be treated almost the same as . The goal of the simplifications is to extract as much type information as possible from a type equation, and thus to infer type arguments where a precise implementation may fail, because we can.

    Simplifying X :≡ Y

    Go’s assignability rules are pretty complicated, but most of the time we can actually get by with type identity, or a slight variation of it. As long as we find potential type arguments, we’re happy, exactly because type inference is still followed by type instantiation and function invocation. If inference finds a type argument where it shouldn’t, it’ll be caught later. Thus, when matching for assignability, we make the following adjustments to the unfication algorithm:

    • When a named (defined) type is matched against a type literal, their underlying types are compared instead.
    • When comparing channel types, channel directions are ignored.

    Furthermore, the assignment direction is ignored: X :≡ Y is treated like Y :≡ X.

    These adjustments apply only at the top level of a type structure: for instance, per Go’s assignability rules, a named map type may be assigned to an unnamed map type, but the key and element types must still be identical. With these changes, unification for assignability becomes a (minor) variation of unification for type identity. The following example illustrates this.

    Let’s assume we are passing a value of our earlier List type (defined as type List []int) to a function parameter of type []E where E is a bound type parameter (i.e., E is declared by the generic function that is being called). This leads to the type equation []E :≡ List. Attempting to unify these two types requires comparing []E with List These two types are not identical, and without any changes to how unification works, it will fail. But because we are unifying for assignability, this initial match doesn’t need to be exact. There’s no harm in continuing with the underlying type of the named type List: in the worst case we may infer an incorrect type argument, but that will lead to an error later, when assignments are checked. In the best case, we find a useful and correct type argument. In our example, inexact unification succeeds and we correctly infer int for E.

    Simplifying X ∈ Y

    Being able to simplify the constraint satisfaction relation is even more important as constraints can be very complex.

    Again, constraint satisfaction is checked at instantiation time, so the goal here is to help type inference where we can. These are typically situations where we know the structure of a type parameter; for instance we know that it must be a slice type and we care about the slice’s element type. For example, a type parameter list of the form [P ~[]E] tells us that whatever P is, its underlying type must be of the form []E. These are exactly the situations where the constraint has a core type.

    Therefore, if we have an equation of the form

    P ∈ constraint               // or
    P ∈ ~constraint
    

    and if core(constraint) (or core(~constraint), respectively) exists, the equation can be simplified to

    P        ≡ core(constraint)
    under(P) ≡ core(~constraint)  // respectively
    

    In all other cases, type equations involving constraints are ignored.

    Expanding inferred types

    If unification is successful it produces a mapping from type parameters to inferred type arguments. But unification alone doesn’t ensure that the inferred types are free of bound type parameters. To see why this is the case, consider the generic function g below which is invoked with a single argument x of type int:

    func g[A any, B []C, C *A](x A) { … }
    
    var x int
    g(x)
    

    The type constraint for A is any which doesn’t have a core type, so we ignore it. The remaining type constraints have core types and they are []C and *A respectively. Together with the argument passed to g, after minor simplifications, the type equations are:

        A :≡ int
        B ≡ []C
        C ≡ *A
    

    Since each equation pits a type parameter against a non-type parameter type, unification has little to do and immediately infers

        A ➞ int
        B ➞ []C
        C ➞ *A
    

    But that leaves the type parameters A and C in the inferred types, which is not helpful. Like in high school algebra, once an equation is solved for a variable x, we need to substitute x with its value throughout the remaining equations. In our example, in a first step, the C in []C is substituted with the inferred type (the “value”) for C, which is *A, and we arrive at

        A ➞ int
        B ➞ []*A    // substituted *A for C
        C ➞ *A
    

    In two more steps we replace the A in the inferred types []*A and *A with the inferred type for A, which is int:

        A ➞ int
        B ➞ []*int  // substituted int for A
        C ➞ *int    // substituted int for A
    

    Only now inference is done. And like in high school algebra, sometimes this doesn’t work. It’s possible to arrive at a situation such as

        X ➞ Y
        Y ➞ *X
    

    After one round of substitutions we have

        X ➞ *X
    

    If we keep going, the inferred type for X keeps growing:

        X ➞ **X     // substituted *X for X
        X ➞ ***X    // substituted *X for X
        etc.
    

    Type inference detects such cycles during expansion and reports an error (and thus fails).

    Untyped constants

    By now we have seen how type inference works by solving type equations with unification, followed by expansion of the result. But what if there are no types? What if the function arguments are untyped constants?

    Another example helps us shed light on this situation. Let’s consider a function foo which takes an arbitrary number of arguments, all of which must have the same type. foo is called with a variety of untyped constant arguments, including a variable x of type int:

    func foo[P any](...P) {}
    
    var x int
    foo(x)         // P ➞ int, same as foo[int](x)
    foo(x, 2.0)    // P ➞ int, 2.0 converts to int without loss of precision
    foo(x, 2.1)    // P ➞ int, but parameter passing fails: 2.1 is not assignable to int
    

    For type inference, typed arguments take precedence over untyped arguments. An untyped constant is considered for inference only if the type parameter it’s assigned to doesn’t have an inferred type yet. In these first three calls to foo, the variable x determines the inferred type for P: it’s the type of x which is int. Untyped constants are ignored for type inference in this case and the calls behave exactly as if foo was explicitly instantiated with int.

    It gets more interesting if foo is called with untyped constant arguments only. In this case, type inference considers the default types of the untyped constants. As a quick reminder, here are the possible default types in Go:

    Example     Constant kind              Default type    Order
    
    true        boolean constant           bool
    42          integer constant           int             earlier in list
    'x'         rune constant              rune               |
    3.1416      floating-point constant    float64            v
    -1i         complex constant           complex128      later in list
    "gopher"    string constant            string
    

    With this information in hand, let’s consider the function call

    foo(1, 2)    // P ➞ int (default type for 1 and 2)
    

    The untyped constant arguments 1 and 2 are both integer constants, their default type is int and thus it’s int that is inferred for the type parameter P of foo.

    If different constants—say untyped integer and floating-point constants—compete for the same type variable, we have different default types. Before Go 1.21, this was considered a conflict and led to an error:

    foo(1, 2.0)    // Go 1.20: inference error: default types int, float64 don't match
    

    This behavior was not very ergonomic in use and also different from the behavior of untyped constants in expressions. For instance, Go permits the constant expression 1 + 2.0; the result is the floating-point constant 3.0 with default type float64.

    In Go 1.21 the behavior was changed accordingly. Now, if multiple untyped numeric constants are matched against the same type parameter, the default type that appears later in the list of int, rune, float64, complex is selected, matching the rules for constant expressions:

    foo(1, 2.0)    // Go 1.21: P ➞ float64 (larger default type of 1 and 2.0; behavior like in 1 + 2.0)
    

    Special situations

    By now we’ve got the big picture about type inference. But there are a couple of important special situations that deserve some attention.

    Parameter order dependencies

    The first one has to do with parameter order dependencies. An important property we want from type inference is that the same types are inferred irrespective of the order of the function parameters (and corresponding argument order in each call of that function).

    Let’s reconsider our variadic foo function: the type inferred for P should be the same irrespective of the order in which we pass the arguments s and t (playground).

    func foo[P any](...P) (x P) {}
    
    type T struct{}
    
    func main() {
        var s struct{}
        var t T
        fmt.Printf("%T\n", foo(s, t))
        fmt.Printf("%T\n", foo(t, s)) // expect same result independent of parameter order
    }
    

    From the calls to foo we can extract the relevant type equations:

    𝑻(x) :≡ 𝑻(s) => P :≡ struct{}    // equation 1
    𝑻(x) :≡ 𝑻(t) => P :≡ T           // equation 2
    

    Sadly, the simplified implementation for :≡ produces an order dependency:

    If unification starts with equation 1, it matches P against struct; P doesn’t have a type inferred for it yet and thus unification infers P ➞ struct{}. When unification sees type T later in equation 2, it proceeds with the underlying type of T which is struct{}, P and under(T) unify, and unification and thus inference succeeds.

    Vice versa, if unification starts with equation 2, it matches P against T; P doesn’t have a type inferred for it yet and thus unification infers P ➞ T. When unification sees struct{} later in equation 1, it proceeds with the underlying type of the type T inferred for P. That underlying type is struct{}, which matches struct in equation 1, and unification and thus inference succeeds.

    As a consequence, depending on the order in which unification solves the two type equations, the inferred type is either struct{} or T. This is of course unsatisfying: a program may suddenly stop compiling simply because arguments may have been shuffled around during a code refactoring or cleanup.

    Restoring order independence

    Luckily, the remedy is fairly simple. All we need is a small correction in some situations.

    Specifically, if unification is solving P :≡ T and

    • P is a type parameter which already has inferred a type A: P ➞ A
    • A :≡ T is true
    • T is a named type

    then set the inferred type for P to T: P ➞ T

    This ensures that P is the named type if there is choice, no matter at which point the named type appeared in a match against P (i.e., no matter in which order the type equations are solved). Note that if different named types match against the same type parameter, we always have a unfication failure because different named types are not identical by definition.

    Because we made similar simplifications for channels and interfaces, they also need similar special handling. For instance, we ignore channel directions when unifying for assignability and as a result may infer a directed or bidirectional channel depending on argument order. Similar problems occur with interfaces. We’re not going to discuss these here.

    Going back to our example, if unification starts with equation 1, it infers P ➞ struct{} as before. When it proceeds with equation 2, as before, unification succeeds, but now we have exactly the condition that calls for a correction: P is a type parameter which already has a type (struct{}), struct{}, struct{} :≡ T is true (because struct{} ≡ under(T) is true), and T is a named type. Thus, unification makes the correction and sets P ➞ T. As a result, irrespective of the unification order, the result is the same (T) in both cases.

    Self-recursive functions

    Another scenario that causes problems in a naive implementation of inference is self-recursive functions. Let’s consider a generic factorial function fact, defined such that it also works for floating-point arguments (playground). Note that this is not a mathematically correct implementation of the gamma function, it is simply a convenient example.

    func fact[P ~int | ~float64](n P) P {
        if n <= 1 {
            return 1
        }
        return fact(n-1) * n
    }
    

    The point here is not the factorial function but rather that fact calls itself with the argument n-1 which is of the same type P as the incoming parameter n. In this call, the type parameter P is simultaneously a bound and a free type parameter: it is bound because it is declared by fact, the function that we are calling recursively. But it is also free because it is declared by the function enclosing the call, which happens to also be fact.

    The equation resulting from passing the argument n-1 to parameter n pits P against itself:

    𝑻(n) :≡ 𝑻(n-1) => P :≡ P
    

    Unification sees the same P on either side of the equation. Unification succeeds since both types are identical but there’s no information gained and P remains without an inferred type. As a consequence, type inference fails.

    Luckily, the trick to address this is simple: Before type inference is invoked, and for (temporary) use by type inference only, the compiler renames the type parameters in the signatures (but not the bodies) of all functions involved in the respective call. This doesn’t change the meaning of the function signatures: they denote the same generic functions irrespective of what the names of the type parameters are.

    For the purpose of this example, let’s assume the P in the signature of fact got renamed to Q. The effect is as if the recursive call was done indirectly through a helper function (playground):

    func fact[P ~int | ~float64](n P) P {
        if n <= 1 {
            return 1
        }
        return helper(n-1) * n
    }
    
    func helper[Q ~int | ~float64](n Q) Q {
        return fact(n)
    }
    

    With the renaming, or with the helper function, the equation resulting from passing n-1 to the recursive call of fact (or the helper function, respectively) changes to

    𝑻(n) :≡ 𝑻(n-1) => Q :≡ P
    

    This equation has two type parameters: the bound type parameter Q, declared by the function that is being called, and the free type parameter P, declared by the enclosing function. This type equation is trivially solved for Q and results in the inference Q ➞ P which is of course what we’d expect, and which we can verify by explicitly instantiating the recursive call (playground):

    func fact[P ~int | ~float64](n P) P {
        if n <= 1 {
            return 1
        }
        return fact[P](n-1) * n
    }
    

    What’s missing?

    Conspicuously absent from our description is type inference for generic types: currently generic types must always be explicitly instantiated.

    There are a couple of reasons for this. First of all, for type instantiation, type inference only has type arguments to work with; there are no other arguments as is the case for function calls. As a consequence, at least one type argument must always be provided (except for pathological cases where type constraints prescribe exactly one possible type argument for all type parameters). Thus, type inference for types is only useful to complete a partially instantiated type where all the omitted type arguments can be inferred from the equations resulting from type constraints; i.e., where there are at least two type parameters. We believe this is not a very common scenario.

    Second, and more pertinent, type parameters allow an entirely new kind of recursive types. Consider the hypothetical type

    type T[P T[P]] interface{ … }
    

    where the constraint for P is the type being declared. Combined with the ablity to have multiple type parameters that may refer to each other in complex recursive fashion, type inference becomes much more complicated and we don’t fully understand all the implications of that at the moment. That said, we believe it shouldn’t be too hard to detect cycles and proceed with type inference where no such cycles exist.

    Finally, there are situations where type inference is simply not strong enough to make an inference, typically because unification works with certain simplifying assumptions such as the ones described earlier in this post. The primary example here is constraints which have no core type, but where a more sophisticated approach might be able to infer type information anyway.

    These are all areas where we may see incremental improvements in future Go releases. Importantly, we believe that cases where inference currently fails are either rare or unimportant in production code, and that our current implementation covers a large majority of all useful code scenarios.

    That said, if you run into a situation where you believe type inference should work or went astray, please file an issue! As always, the Go team loves to hear from you, especially when it helps us making Go even better.


Random expired ±

2 links selected from 564 expired links

Expired ±

564 links expired today Wed, Sep.25, 2024
  1. The Book

    This is the story of Simon Wardley. Follow his journey from bumbling and confused CEO lost in the headlights of change to someone with a vague idea of what they're doing. (Open link)

  2. https://rust-book.cs.brown.edu/

    Welcome to the Rust Book experiment, and thank you for your participation! First, we want to introduce you to the new mechanics of this experiment. The main mechanic is quizzes: each page has a few quizzes about the pag (Open link)

  3. The Four Innovation Phases of Netflix’s Trillions Scale Real-time Data Infrastructure | by Zhenzhong Xu | Feb, 2022 | Medium

    The blog post will share the four phases of Real-time Data Infrastructure’s iterative journey in Netflix (2015-2021). For each phase, we will go over the evolving business motivations, the team’s unique challenges, the (Open link)

  4. Not your grandfather’s logs — A Java library’s new approach to observability | by Roni Dover | Apr, 2023 | Better Programming

    A while back, I wrote about the fact that logs need an overhaul, and that practices that were relevant when logs were still text messages in files may no longer be relevant in an age when logs traces… (Open link)

  5. The Kaizen Way

    Are you looking for a new approach to health? Do you want to finally get the results you have been hoping for? How do you find a practitioner that is willing to try a different approach and guide you through your journey (Open link)

  6. JDK 21 Release Notes

    JDK 21 Release Notes JEPs JEP 430 String Templates (Preview) Enhance the Java programming language with string templates. String templates complement Java's existing string literals and text blocks by coupling literal (Open link)

  7. What's in a Good Error Message? - Gunnar Morling

    In a way, an error message tells a story; and as with every good story, you need to establish some context about its general settings. For an error message, this should tell the recipient what the code in question was tr (Open link)

  8. Convey

    2022 February 01 16:21 stuartscott 1473754¤ 1240149¤ You may have noticed that the January edition of the Convey Digest looks a little different from the previous ones - the color scheme is now based on the dominant (Open link)

  9. The Grug Brained Developer

    Introduction this collection of thoughts on software development gathered by grug brain developer grug brain developer not so smart, but grug brain developer program many long year and learn some things although mostly s (Open link)

  10. Tripsy 2.15 Adds Weather Forecasts, Time Zone Support, and Other Customization Options - MacStories

    Tripsy is more than just an app for storing details about your upcoming trips. It does that and does it well, but it’s also a great way to revisit old trips and get inspired about places you want to visit in the future. (Open link)

  11. Diátaxis

    The Diátaxis framework solves the problem of structure in technical documentation, making it easier to create, maintain and use. (Open link)

  12. Let's talk SkipList

    BackgroundSkipLists often come up when discussing “obscure” data-structures but in reality they are not that obscure, in fact many of the production grade softwares actively use them. In this post I’ll try to go into Ski (Open link)

  13. 7 days ago

    This article has a large gap in the story: it ignores sensor data sources, which are both the highest velocity and highest volume data models by multiple orders of magnitude. They have become ubiquitous in diverse, mediu (Open link)

  14. Beyond Microservices: Streams, State and Scalability

    Gwen Shapira talks about how microservices evolved in the last few years, based on experience gained while working with companies using Apache Kafka to update their application architecture. (Open link)

  15. Welcome - Rambling Readers

    Search Scan Barcode Username: Password: Forgot your password? Log in Rambling Readers Read | Review | Discover DECENTRALIZED FRIENDLY ANTI-CORPORATE Rambling Readers is a friendly community of book lovers. You can tr (Open link)

  16. here

    Sample code and instructions for steps through different container image build options. - GitHub - maeddes/options-galore-container-build: Sample code and instructions for steps through different container image build op (Open link)

  17. https://programmerweekly.us2.list-manage.com/track/click?u=72f68dcee17c92724bc7822fb&id=c6a9958764&e=d7c3968f32

    Ever since I started to work on the Apache APISIX project, I’ve been trying to improve my knowledge and understanding of REST RESTful HTTP APIs. For this, I’m reading and watching the following sources: Books. At the mom (Open link)

  18. Top 10 Architecture Characteristics / Non-Functional Requirements with Cheatsheet | by Love Sharma | Jun, 2022 | Dev Genius

    Imagine you are buying a car. What essential features do you need in it? A vehicle should deliver a person from point A to point B. But what we also check in it is Safety, Comfort, Maintainability… (Open link)

  19. Manhattan Phoenix review: epic history of how New York was forged by fire – and water | Books | The Guardian

    Daniel Levy pins the great fire of 1835 as the birth event of modern Manhattan in a tale as teeming as the city itself (Open link)

  20. The Go Memory Model

    Table of ContentsIntroductionAdviceInformal OverviewMemory ModelImplementation Restrictions for Programs Containing Data RacesSynchronizationInitializationGoroutine creationGoroutine destructionChannel communicationLocks (Open link)

  21. Overheard at QCon 2022: Navigate complex environment and evolving relationships | by McKinsey Digital | McKinsey Digital Insights | Jan, 2023 | Medium

    We recently had the pleasure of participating in QCon, a global conference that gathers the best engineers from top-notch innovation companies. The event covers a wide range of relevant software… (Open link)

  22. You and your mind garden

    In French, “cultiver son jardin intérieur” means to tend to your internal garden—to take care of your mind. The garden metaphor is particularly apt: taking care of your mind involves cultivating your curiosity (the seeds (Open link)

  23. User space

    For the term "user space" as used in Wikipedia, see Wikipedia:User pages. "Kernel space" redirects here. For the mathematical definition, see Null space. This article needs additional citations for verification. Please h (Open link)

  24. Shields Down

    Resignations happen in a moment, and it’s not when you declare, “I’m resigning.” The moment happened a long time ago when you received a random email from a good friend who asked, “I know you’re really happy with your cu (Open link)

  25. What's in a Good Error Message?

    In a way, an error message tells a story; and as with every good story, you need to establish some context about its general settings. For an error message, this should tell the recipient what the code in question was tr (Open link)

  26. How can I permanently add my SSH private key to Keychain so it is automatically available to ssh? - Ask Different

    Log in Sign up Ask Different is a question and answer site for power users of Apple hardware and software. It only takes a minute to sign up. Sign up to join this community Anybody can ask a question Anybody can answe (Open link)

  27. Maintaining a medium-sized Java library in 2022 and beyond

    scc --exclude-dir docs/book ─────────────────────────────────────────────────────────────────────────────── Language Files Lines Blanks Comments Code Complexity ──────────────────────────────── (Open link)

  28. Everlog

    Being a creature of habit, I don’t tend to change up my tech routine very often. Once I find a workflow that clicks for me, I usually stick with it. Why fix what isn’t broken? But lately, for one reason or another, I’ve (Open link)

  29. Gonzo journalism

    The "Gonzo fist", characterized by two thumbs and four fingers holding a peyote button, was originally used in Hunter S. Thompson's 1970 campaign for sheriff of Pitkin County, Colorado. It has since evolved into a symbol (Open link)

  30. A Better Way to Manage Projects

    The GOVNO framework is a novel approach to project management that aims to improve upon the shortcomings of the popular scrum methodology. Each letter of the acronym represents a key aspect of the framework: G: Governan (Open link)

  31. Optimizing Distributed Joins: The Case of Google Cloud Spanner and DataStax Astra DB | by DataStax | Building Real-World, Real-Time AI | Medium

    In this post, learn how relational and NoSQL databases, Google Cloud Spanner and DataStax Astra DB, optimize distributed joins for real-time applications. Distributed joins are commonly considered to… (Open link)

  32. How to Do Great Work

    July 2023 If you collected lists of techniques for doing great work in a lot of different fields, what would the intersection look like? I decided to find out by making it. Partly my goal was to create a guide that cou (Open link)

  33. Bicycle

    There is something delightful about riding a bicycle. Once mastered, the simple action of pedaling to move forward and turning the handlebars to steer makes bike riding an effortless activity. In the demonstration below, (Open link)